ICALP 2024 | 广义偏序集排序

关键词：排序，图算法，近似算法

导  读

本文是对 ICALP 2024 会议上发表的论文 Algorithms for the Generalized Poset Sorting Problem 的论文解读。本论文由北京大学姜少峰课题组与上海交通大学合作完成。论文作者遵循姓氏排名，为北京大学助理教授姜少峰、上海交通大学硕士生王文茜、北京大学博士生张宇博、上海交通大学副教授张宇昊。论文研究了广义排序问题在偏序集上的推广，并将推广的结果应用于带比较代价的排序问题上，提出了第一个在比较代价只有常数种取值时可以做到亚线性近似比的算法。

↑扫码跳转论文

论文链接：

https://arxiv.org/abs/2304.01623

01

问题背景

广义排序是一个排序问题的变种，与排序问题相同，算法接受待排序的元素作为输入，需要对给定的元素进行次数尽可能少的比较，来揭示这些元素之间所有的大小关系，即给出它们按照大小关系的排序。与最基本的排序问题不同的是，排序算法只能从输入中给定的元素对中选择需要进行比较的对象，没有在输入中给出的元素对都无法直接进行比较。

本文将广义排序问题拓展到偏序集上，待排序的元素不再拥有一个全序，排序算法接受可以进行直接比较的元素对作为输入，通过尽可能少的比较来推断出所有输入元素对之间的大小关系。

作为广义排序问题的推广，广义偏序集问题显著地难于原问题。在广义排序问题中，由于待排序的元素之间的大小关系是全序，尽管排序算法只能选择给定的元素对进行比较，但每次都会得到形如  或  的确定回答。而在广义偏序集排序问题中，排序算法可能会得到“  不可比”的回答，而一对不可比的元素为排序提供的信息量非常小，大大提高了排序的难度。我们也可以对输入进行限制，保证每一对可以直接比较的元素在偏序集中都是可比的，我们将这种仅有可比边的广义偏序集排序问题简记为 GPSC 问题。

带比较代价的排序问题是广义排序问题在另一个方向上的推广。在带比较代价的排序问题中，比较任意两个元素  都需要付出  的代价，其中代价函数  在输入中给定。广义排序问题就是所有比较代价都是1或正无穷的特殊情况。该问题曾被认为不存在亚线性近似比的算法，但 [Goswami, Jacob, 2022] 的研究表明这种说法并不准确。在排序算法里，一般认为最优解必须要比较每一对相邻的元素对来确认这个全序的正确性，在这种最优解的定义下之前的反例并不成立。

02

问题设定与结果

在广义偏序集排序问题中，排序算法接受一个  个点  条边的无向图作为输入，无向图的点集表示待排序的元素集，而无向图的边集表示排序算法可以比较的元素对。排序算法的目标是使用最少的比较次数推断出每条边的两个端点之间的大小关系，并以一张有向图的形式输出。由于广义偏序集排序是偏序集排序问题的推广，因此任何排序算法都至少需要  次询问才能完成排序，其中  是排序算法输出的有向图的最长反链长度（即最大的任意两点间都不存在路径的点集）。

由于一般图上的广义偏序集排序问题难以解决，本文主要研究了随机图和完全二分图上的广义偏序集问题：

随机图：当输入无向图是某个极小有向无环图与随机图  的并时，本文提出了一种可以在  次比较内完成排序的算法。（极小即  这三条有向边不会同时都存在）当该算法被用于解决随机图上的广义排序问题时（即  的特例），该算法的比较次数为  ，接近于最优算法的比较次数  。

完全二分图：由于一般二分图上的广义偏序集排序问题与原问题同等困难，本文主要考虑输入无向图是完全二分图的情况，并提出了一种可以在  次询问内完成排序的算法。

在 GPSC 问题中，由于每个可以直接比较的元素对在偏序集中都是可比的，我们可以对广义排序算法的一些思路进行推广来解决 GPSC 问题。本文提出了一种可以在  次比较内完成排序的算法，接近于目前广义排序问题的最优结果  次比较。

在带比较代价的排序问题中，我们可以将无向图中的边按照某个阈值划分为较便宜的边和较贵的边，所有便宜的边共同构成了一个偏序集，对这个偏序集排序就是一个 GPSC 子问题。通过猜测合适的阈值，我们可以将带比较代价的排序问题转化为若干个 GPSC 子问题来求解。最终的近似比为  ，其中  为比较代价的取值种类数。该算法是第一个在比较代价有常数种取值时能实现亚线性近似比的算法。

03

总  结

本文研究了广义排序问题在偏序集上的一个自然推广，由于引入了不可比较的点对，新的推广相比于原问题要困难很多。本文抛砖引玉，给出了特殊情况下的解决方案，并通过带比较代价的排序问题的新算法，展示了广义偏序集排序问题的研究价值。

图文 | 张宇博

北京大学姜少峰课题组

姜少峰课题组近期动态

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点击“阅读原文”转论文地址